package com.explorati.LeetCode120.minimumTotal;

import org.omg.PortableInterceptor.INACTIVE;

import java.util.ArrayList;
import java.util.List;

/**
 * @ Author : Weijian_Wang
 * @ Date : Created in 16:43 2020/10/6 0006
 * @ Description ：
 */
public class Solution1 {

    /**
     * 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
     *
     * [
     *      [2],
     *     [3,4],
     *    [6,5,7],
     *   [4,1,8,3]
     * ]
     *
     * @param triangle
     * @return
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        //自顶向下 二维数组中存放 从上向下 加和
        //优化： res中只用到了res[i - 1][...]相关的值
        int[][] res = new int[2][n];
        //转移方程： f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + res[i][j]
        //边界：左边界 f[i][0] = f[i - 1][0] + res[i][0] 右边界 f[i][j] = f[i - 1][j - 1] + res[i][j]
        //初始化：res[0][0] = triangle.get(0).get(0)

        res[0][0] = triangle.get(0).get(0);

        //纵向
        for(int i = 1; i < n; i ++) {
            //当前行 第一次为1
            int cur = i % 2;
            //上一行  第一次为0，即res[0][...]
            int pre = 1 - cur;
            //左边界
            res[cur][0] = res[pre][0] + triangle.get(i).get(0);
            for(int j = 1; j < i; j ++) {
                res[cur][j] = Math.min(res[pre][j - 1], res[pre][j]) + triangle.get(i).get(j);
            }
            //右边界
            res[cur][i] = res[pre][i - 1] + triangle.get(i).get(i);
        }

        //在最后一行找寻最小值
        int minValue = res[(n - 1) % 2][0];
        for(int i = 1; i < n; i ++) {
            if(res[(n - 1) % 2][i] < minValue) {
                minValue = res[(n - 1) % 2][i];
            }
        }

        return minValue;
    }
    public static void main(String[] args) {
        List<List<Integer>> triangle = new ArrayList<>();
        List<Integer> row1 = new ArrayList<>();
        row1.add(2);
        List<Integer> row2 = new ArrayList<>();
        row2.add(3);
        row2.add(4);
        List<Integer> row3 = new ArrayList<>();
        row3.add(6);
        row3.add(5);
        row3.add(7);
        List<Integer> row4 = new ArrayList<>();
        row4.add(4);
        row4.add(1);
        row4.add(8);
        row4.add(3);

        triangle.add(row1);
        triangle.add(row2);
        triangle.add(row3);
        triangle.add(row4);

        System.out.println("....");
    }
}
